use serde::{Deserialize, Serialize};
use serde_with::*;
use std::collections::{BTreeMap, HashMap};
use std::fs::File;
use std::rc::Rc;

#[serde_as]
#[derive(Deserialize, Serialize, Debug)]
#[serde(transparent)]
struct Group {
    #[serde_as(as = "Map<_, _>")]
    inner: Vec<(String, Vec<String>)>,
}
impl Group {
    fn root_or_insert(
        ref_map: &mut HashMap<Rc<String>, Rc<String>>,
        node: Rc<String>,
    ) -> Rc<String> {
        let parent = ref_map
            .entry(node.clone())
            .or_insert_with(|| node.clone())
            .clone();
        let mut parent = &parent;
        loop {
            let parent_2 = ref_map.get(parent).unwrap();
            if parent == parent_2 {
                break;
            }
            parent = parent_2;
        }
        parent.clone()
    }
    fn union_count(self) -> usize {
        let mut ref_map = HashMap::new();
        for (r1, r2_vec) in self.inner {
            let r1 = Rc::new(r1);
            let root_1 = Self::root_or_insert(&mut ref_map, r1.clone());
            for r2 in r2_vec {
                let r2 = Rc::new(r2);
                let root_2 = Self::root_or_insert(&mut ref_map, r2.clone());
                ref_map.insert(root_2.clone(), root_1.clone());
            }
        }
        ref_map.iter().filter(|(k, v)| k == v).count()
    }
}
pub fn count_provinces() -> String {
    let input = File::open("district.json").unwrap();
    serde_json::from_reader::<_, BTreeMap<String, Group>>(input)
        .unwrap()
        .into_values()
        .map(|g| g.union_count().to_string())
        .collect::<Vec<_>>()
        .join(",")
}
